package com.bolang.onlycode.demo.Cache;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 最近最少使用算法
 * 算法核心实现：散列表+双向链表
 * 算法核心功能
 * 1：添加缓存（先判断散列表中是否存在，如果存在，则将该缓存移动到链尾）
 * 2：查找缓存（因为是散列表，所以时间复杂度接近O（1））
 * 3：删除缓存
 */
public class LRUcache {
    private HashMap<String,Node> map =new HashMap<>();
    private Node head ;
    private Node tail;
    private int cacheSize=5;
    public LRUcache(){
        head =new Node();
    }
    public int size(){
        return map.size();
    }
    /**
     * 添加缓存
     * @param key
     * @param value
     */
    public void addCache(String key,String value){
        if(map.containsKey(key)){
           Node node =map.get(key);
           if(node.next!=null){
               node.pre.next=node.next;
               node.next.pre=node.pre;
               tail.next=node;
               node.pre=tail;
               node.next=null;
               tail=node;
           }
        }else {
            Node node =new Node(key,value);
            if(map.size()==cacheSize){
                Node temp=head.next;
                map.remove(temp.key);
                head.next=temp.next;
                temp.next.pre=head;
                node.pre=tail;
                tail.next=node;
                tail=node;
            }else {
                if(tail==null){
                    node.pre=head;
                    head.next=node;
                }else {
                    node.pre=tail;
                    tail.next=node;
                }
                tail=node;
            }
            map.put(key,node);
        }
    }
    public String getCache(String key){
        if(map.containsKey(key)){
            Node node = map.get(key);
            if(node.next!=null){
                node.pre.next=node.next;
                node.next.pre=node.pre;
                tail.next=node;
                node.pre=tail;
                node.next=null;
                tail=node;
            }
            return node.value;
        }else {
            return null;
        }
    }
    class Node{
        Node pre;
        Node next;
        String key;
        String value;
        public Node(String key,String value){
            this.key=key;
            this.value=value;
        }
        public Node(){
        }

    }
}
